536. Construct Binary Tree from String
Medium

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

 

Example 1:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s consists of digits, '(', ')', and '-' only.
Accepted
48.2K
Submissions
91.2K
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.69 (13 votes)

Premium

Solution


Overview

This is a really useful problem to work on since this is a part of the general umbrella of problems which are like Serialize and Deserialize some data structure. This is important if we want to save a tree (a custom object with some special properties and fields) to a file, a database, or as a string someplace essentially. In this problem we are given a string representation of a tree i.e. we are given the serialized version of the tree and we have to deserialize it and return the TreeNode object representing the root of the tree (since the rest of the tree is trackable via the root).

A tree (or a graph) has a recursive structure to it i.e. a subtree is a tree in itself. Similarly, we expect the string representation of a tree to also have some kind of a recursive structure and that is what will be used to reconstruct our tree. Let's first take a look at this recursive structure in the string.

Figure 1. The tree and the corresponding string.

Let's look at the subtrees along with their counterparts in the string. Note that we assume the entire string is also enclosed between a pair of brackets thus representing the entire tree.

Figure 2. String split according to the subtrees.

So we can see the recursive build-up of the string and we are going to leverage that property to come up with a solution. Since this problem involves a recursive property, we will look at a solution based on recursion, and then, we will convert that solution to one using a stack as opposed to the memory stack used in the recursive approach.



Approach 1: Recursion

Intuition

The idea here is very simple. An opening bracket represents the start of a new tree (subtree really). Thus, whenever we encounter a new opening bracket, we make a new recursion call. A recursion call to our function will essentially return the root of a properly built tree with all the required TreeNode objects and proper connections set up between them. Thus, making a new recursive call upon encountering an opening bracket is essentially calling our function to build the subtree and return the root node.

We know when to make a new recursive call, but, when do we stop really? We stop when we encounter a closing bracket. That's because a closing bracket will be the end of the most recent subtree that we're building in our recursion. We assume that a particular closing bracket matches with the nearest opening bracket we would have encountered previously when we made the recursive call. Let's put all this information into an algorithm with steps.

Algorithm

  1. Let's define a couple of internal functions that we will be using along the way. The first one is called getNumber and it returns the integer number/value that the current TreeNode is supposed to have. It takes the string and the current index as inputs. We iterate until we no longer encounter a digit or we reach the end of the string. We stick all the digits together and get a number. Also, we take care of the sign - in case one exists in the beginning which would indicate a negative value for the node.

  2. The next function we define is our recursive function called str2treeInternal which does all the heavy lifting for us. It also takes the string and the index of the current character as inputs and returns a pair of the TreeNode representation of the current subtree and also the index of the next character to be processed in the string. This index manipulation is important because we don't want to parse the string twice to figure out the boundaries for the children subtrees.

  3. Whenever the function str2treeInternal is called, we expect that the current subtree will all its children and descendants will be constructed and returned. There are 4 steps we take inside this function of ours.

    1. Firstly we check for the termination condition i.e. if there are no more characters left in the string to process.

      Figure 3. Sample subtrees which we will consider for the algorithm.

    2. Next, we get the value for the root node of this tree. This is an invariant here. We will never find any brackets before we get the value for the root node.

    3. Once we have the value, we form the root node.

    4. Then, we check for an opening bracket (make sure to check for the end of string conditions always). If there is one, we make a recursive call and use the node returned as the left child of the current node.

    5. Finally, we check if there's another opening bracket. If there is one, then it represents our right child and we again make a recursive call to construct that and make the right connection.

  4. We return the construct root node and also the correct index. For the index, we check if it points to a closing bracket, we move one step forward. Else, we stay at the current spot and let the caller function decide how to proceed/process.

Implementation

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN represents the number of characters in the string representation. This is because each character is processed exactly once and we need to process the entire string to form our tree.

  • Space Complexity: O(H)O(H) where HH represents the height of the tree. We don't have any information about if the tree is balanced or not and so, in the worst case when the tree would be skewed left (can't be right according to the problem), we will have a recursion stack consisting of NN calls and hence, the overall space complexity can be O(N)O(N);



Approach 2: Stack

Intuition

The main problem with a recursive solution is the stack limitation. We might run into stack-overflow problems if the tree is too tall and the system's stack is low on resources. Hence, we prefer to use our own stack and that is the variation which we will explore in this solution. The overall idea remains the same as the previous approach and for that matter, even the complexities remain the same. The only thing that changes is a recursive vs iterative approach.

The algorithm presented here is completely based on the recursive solution before. The only thing we need to take care of are the different states a particular function call/node can be in during recursion. Notably, there are 3 different states that we need to account for. We won't be using these three states in the code directly but it is important to understand these three possibilities to understand the overall algorithm.

  1. NOT_STARTED ~ This is the initial state that a node is in. Before we even process the left or the right children. In this state, we simply form the value of the root node and then check for the presence of the left child. If the left child exists, we make a recursive call and the returned value is used as the left child.
  2. LEFT_DONE ~ In this state, we are processing our root node given the fact that we're done processing its left subtree. So, the index would be used to check for the presence of a right child and if one exists, we make another recursive call to process the same.
  3. RIGHT_DONE ~ This is the final state of any node where we are done processing the left and the right children and don't need to do anything more.

Algorithm

  1. Let's define a function called getNumber which returns the integer number/value that the current TreeNode is supposed to have. It takes the string and the current index as inputs. We iterate until we no longer encounter a digit or we reach the end of the string. We stick all the digits together and get a number. Also, we take care of the sign - in case one exists in the beginning which would indicate a negative value for the node.
  2. We use a stack for our implementation and it would contain a pair of the node itself and the state it is in. The state can be one of the three described before.
  3. Initially, we push the root node (a new TreeNode essentially) into the stack. Note: that the state of this node is NOT_STARTED.
  4. We iterate over the characters in our string one by one and we do the following at each step:
    1. Pop the node. This will be the root node that we currently process i.e. not the global root node of the tree but rather the root of the current subtree.

    2. If the current character pointed to by the index is a digit or the - character,

      1. that means we have a node that we haven't started processing yet i.e. the NOT_STARTED state. So the first thing we do is to call the getNumber function to get the value for the node and set node.val to this value. Note: the getNumber function progresses the index.
      2. Then, we check for the presence of a left child. We simply check if there are more characters left in the string and the one we have to process now is an opening bracket. If it is, then we do two things:
        • We add the current node back to the queue. At this point, the state of this node would be LEFT_DONE. Again, we don't need the state information anywhere in the code except for reasoning about the algorithm itself.

        • Then, we assign node.left to a new TreeNode and also add it to the queue.

          Figure 4. Process the root node from the string.

          Figure 5. Here we process the left child.

          Figure 6. Complete the processing or the left child.

    3. If the current character is the left bracket i.e. (,

      1. we check for the presence of a right child because we know that the value of the node is already set in the previous step and also, the left child is properly processed at this point.
      2. We check if the current character, if there is one left, is an opening bracket. If it is one then we do the following:
        • We add the current node back to the queue assuming its state to be LEFT_DONE.

        • Then, we assign node.right to a new TreeNode and also add it to the queue.

          Figure 7. Start processing the right child.

    4. We don't do anything if the current character is a closing bracket except for popping the nodes which we already did in step 4.1 here.

      Figure 8. Pop the right child and return the root.

Implementation

Complexity Analysis

The complexity is the same as the previous solution with the only exception that we are now using our own stack instead of relying on the system's stack.

  • Time Complexity: O(N)O(N) where NN represents the number of characters in the string representation. This is because each character is processed exactly once and we need to process the entire string so as to form our tree.

  • Space Complexity: O(H)O(H) where HH represents the height of the tree. We don't have any information about if the tree is balanced or not and so, in the worst case when the tree would be skewed left (can't be right according to the problem), we will have a recursion stack consisting of NN calls and hence, the overall space complexity can be O(N)O(N);


Report Article Issue

Comments: 8
zero_day's avatar
Read More

Easy to understand recursion approach

public class Solution {
private int index = 0;

public TreeNode Str2tree(string s) {
    index = 0;
    return BuildTree(s);
}

private TreeNode BuildTree(string str){
    
    //This is our condition to come out of recurssion
    if(index >= str.Length) return null;
    
    //If current character is closed bracket ')'
    //This means child of the node which called recurrsion is null
    // Also increament the index, to process the next character.
    
    if(str[index] == ')'){
        index++;
        return null;
    }
  
    int val = GetValue(str);
    
    var node = new TreeNode(val);
    
    //Check if we have not reached end of string, 
    //If we have open bracket, means we need to add left child first. 
    //So, call BuildTree to add left child from current position.
    if(index < str.Length  && str[index] =='(')
    {
        index++;
        node.left = BuildTree(str);
    }
    
    //Check if we have not reached end of string, 
    //If we have open bracket, means we need to add right child. 
    //So, call BuildTree to add right child from current position.
    if(index < str.Length  && str[index] =='(')
    {
        index++;
        node.right = BuildTree(str);
    }
    
    //Increase the index, to get pass the closed bracket for the current sub-tree.
    index++;
    
    
    //Return the node created.
    return node;
    
}

private int GetValue(string str)
{
    var valueStr = new StringBuilder();
    
    //Get all possible numerical characters including -ve 
    while(index < str.Length && str[index] != ')' && str[index] != '(')
        valueStr.Append(str[index++]);
    
    //Parse the numerical value.
    return Int32.Parse(valueStr.ToString());
    
}

}

Hope this helps someone :)

8
Reply
Share
Report
Pmenke's avatar
Read More

So does this problem not allow for NULL nodes like in https://leetcode.com/problems/construct-string-from-binary-tree/ ? Confusing how its worded.

Ie. This is an invalid test case according to the console "1(2()(4))(3)"

6
Show 3 replies
Reply
Share
Report
lenchen1112's avatar
Read More

Clean python 3 O(N) with iterator

class Solution:
    def str2tree(self, s: str) -> TreeNode:
        def build(I) -> TreeNode:
            num = ''
            while (nxt := next(I)) not in '()':
                num += nxt
            node = TreeNode(int(num))
            if nxt == '(':
                node.left = build(I)
                if next(I) == '(':
                    node.right = build(I)
                    next(I)  # skip tail ')'
            return node

        return build(iter(s + ')')) if s else None

3
Reply
Share
Report
GavinBelson's avatar
Read More

Should be LC hard

3
Show 1 reply
Reply
Share
Report
serbis's avatar
Read More

For solution 1, it was quite confusing because there is no reason why:

  1. We need to check for the left node when building the right. Problem says the left node will always be populated first. I can see why to include it to make the problem more generalized (possibly), but this check is not needed.
  2. At the end of the helper function, we should always return i + 1. I did not find an example that needed return index.

1
Show 1 reply
Reply
Share
Report
nagakiran1's avatar
Read More

Recursion with Nodes and constructing from ground

Deserialization

class Solution:
def str2tree(self, s: str) -> TreeNode:

    def deserialize(s):
        elems = [s[:2]]
        s = s[2:]
        val = 0
        for i, j in enumerate(s):
            if j=='(':
                val+=1
            elif j==')':
                val-=1
            if val==-1:
                return ''.join(elems)[1:], s[i+2:-1]
            elems.append(j)

        return ''.join(elems)

    def recFun(s):
        [#s](https://leetcode.com/problems/two-sum) = "4(2(3)(1))(6(5))"
        if s=='':
            return None
        if '(' not in s:
            return TreeNode(int(s))

        n= s.split('(')[0]
        pr = '('+'('.join(s.split('(')[1:])

        node = TreeNode(int(n))
        a,b = deserialize(pr)
        node.left = recFun(a)
        node.right = recFun(b)
        return node
    node = recFun(s)
    return node

0
Reply
Share
Report
brucezu's avatar
Read More
0
Reply
Share
Report
ltbtb_rise's avatar
Read More

I sort of took a different approach with my stack solution:

class Solution {
public:
    TreeNode* str2tree(string s) {
        if(s == "") return nullptr;
        
        stack<string> process;
        stack<pair<TreeNode*,int>> nodes;
        
        s = "(" + s + ")";
        
        int level = 0;
        int n = s.length();
        string cur = "";
        
        for(int i=0; i<n; i++)
        {
            if(s[i] == '(') 
            {
                if(cur != "") process.push(cur);
                cur = "";
                level++;
            }
            else if(s[i] == ')')
            {
                string num = cur;
                if(num == "")
                {
                    num = process.top();
                    process.pop();
                }
                
                TreeNode* node = new TreeNode(stoi(num));

                vector<TreeNode*> children;
                while(!nodes.empty() && level < nodes.top().second)
                {
                    if(node->right) node->left = nodes.top().first;
                    else node->right = nodes.top().first;
                    nodes.pop();
                }
                
                if(node->left == nullptr && node->right)
                {
                    node->left = node->right;
                    node->right = nullptr;
                }

                nodes.push({node, level});
                
                cur = "";
                level--;
            }
            else
            {
                cur += s[i];
            }
        }
        
        return nodes.top().first;
    }
};

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium